import java.util.*;

/*
* 算法：直接递归 深度优先遍历+set
*
  1. 取消数组等等，在一个方法中直接递归

  分析：
    时间复杂度：O(n)，其中 n 为二叉搜索树的大小。我们需要遍历整棵树一次。

    空间复杂度：O(n)，其中 n 为二叉搜索树的大小。主要为哈希表的开销，最坏情况下我们需要将每个节点加入哈希表一次。


* */
public class Solution_2 {
    Set<Integer> set =new HashSet<>();
    public boolean findTarget(TreeNode root, int k) {
        if(root==null)
        {
            return false;
        }
        if(set.contains(k-root.val))
        {
            return true;
        }
        set.add(root.val);

        return findTarget(root.left,k)||findTarget(root.right,k);
    }


}
